#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>ret;
        unordered_map<string, int>hash1;
        for (auto& s : words)hash1[s]++;
        int len = words[0].size();
        int m = words.size();
        for (int i = 0;i < len;i++)
        {
            int left = i;
            int right = i;
            unordered_map<string, int>hash2;
            int cnt = 0;
            for (;right + len <= s.size();right += len)
            {
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash2[in] <= hash1[in])cnt++;

                if (right - left + 1 > len * m)
                {
                    string out = s.substr(left, len);

                    if (hash2[out] <= hash1[out])cnt--;
                    hash2[out]--;

                    left += len;
                }
                if (cnt == m)ret.push_back(left);
            }
        }
        return ret;
    }
};